﻿using System;
using System.Collections.Generic;
using System.Data.Common;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _11_Generic
{
    internal class BSTree
    {
        // 二叉搜索树
        // 不会出现重复的数据
        // 数组 查找快 修改慢
        // 链表 修改快 查找满
        // 树   查找快 修改快
        private Node<int>? root;// 根节点

        public BSTree() 
        {
            root = null;
        }

        public Node<int>? Insert(int data)
        {
            Node<int>? node = new Node<int>(data);

            if (root == null)
            {
                // 第一次插入
                root = node;
            }
            else
            {
                Node<int> current = root;
                Node<int> parent = null;
                // 树的插入需要找到空位再插入
                while (current != null)
                {
                    parent = current;
                    if (data < current.Data)
                    {
                        current = current.left;
                    }
                    else if(data > current.Data)
                    {
                        current = current.right;
                    }
                    else 
                    {
                        node = null;
                        return node;
                    }
                }
                if(parent != null && data < parent.Data)
                {
                    parent.left = node;
                }
                if (parent != null && data > parent.Data)
                {
                    parent.right = node;
                }
            }
            return node;
        }

        public void Remove(int data)
        {
            // 前提 找到要删除的节点
            Node<int> parent = null;
            Node<int>? target = root;

            while (target != null)
            {
                if (data < target.Data)
                {
                    parent = target;
                    target = target.left;
                }
                else if(data > target.Data)
                {
                    parent = target;
                    target = target.right;
                }
                else
                {
                    // 删除逻辑
                    if (target.left == null && target.right == null)
                    {
                        // 叶子节点
                        if(parent == null)
                        {
                            // 删除根节点
                            root = null;
                        }
                        else
                        {
                            if (target.Data < parent.Data)
                            {
                                parent.left = null;
                            }
                            else
                            {
                                parent.right = null;
                            }
                        }
                        target = null;
                    }
                    else if (target.left == null && target.right != null)
                    {
                        // 有一个子节点
                        if(parent == null)
                        {
                            root = target.right;
                        }
                        else
                        {
                            if (target.Data < parent.Data)
                            {
                                parent.left = target.right;
                            }
                            else
                            {
                                parent.right = target.right;
                            }
                        }
                        target = null;
                    }
                    else if (target.right == null && target.left != null)
                    {
                        // 有一个子节点
                        if (parent == null)
                        {
                            root = target.left;
                        }
                        else
                        {
                            if (target.Data < parent.Data)
                            {
                                parent.left = target.left;
                            }
                            else
                            {
                                parent.right = target.left;
                            }
                        }
                        target = null;
                    }
                    else if (target.right != null && target.left != null)
                    {
                        // 有两个子节点
                        // 先找到左最大或者有最小
                        Node<int> leftMaxP = target;
                        Node<int> leftMax = target.left;
                        while (leftMax.right != null)
                        {
                            leftMaxP = leftMax;
                            leftMax = leftMax.right;
                        }
                        bool isLeft = leftMax.Data < leftMaxP.Data;
                        // 交换data
                        target.Data = leftMax.Data;
                        leftMax.Data = data;
                        // 删除交换后的节点
                        // 左最大或右最小最多只会有一个子节点
                        if(isLeft)
                        {
                            leftMaxP.left = leftMax.left;
                        }
                        else
                        {
                            leftMaxP.right = leftMax.left;
                        }
                        target = null;
                    }
                }
            }
            // 没找到就不删
            if (target == null) return;
            
        }

        //Node<int>? Find(int data, out Node<int>? parent)
        //{
        //    Node<int>? current = root;
        //    parent = root;
        //    while (current != null)
        //    {
        //        if (data < current.Data)
        //        {
        //            parent = current;
        //            current = current.left;
        //        }
        //        else if (data > current.Data)
        //        {
        //            parent = current;
        //            current = current.right;
        //        }
        //        else
        //        {
        //            return current;
        //        }
        //    }
        //    return current;
        //}

        int Min(Node<int> node)
        {
            int min = node.Data;
            while(node.left != null)
            {
                min = node.left.Data;
                node = node.left;
            }
            return min;
        }

        public void Print()
        {
            // 树的遍历
            // 广度优先 BFS
            // 深度优先 DFS
            // 前序 中序 后序
            // 中序输出的结果是有序的
            BFS(root);
        }

        void DFS(Node<int>? node)
        {
            // 当我们想要使用递归时 一定要注意脱出条件
            if (node == null) return;

            Console.WriteLine(node.Data);
            DFS(node.left);
            DFS(node.right);

        }

        void BFS(Node<int>? node)
        {
            if(node == null)return;

            Queue<Node<int>> queue = new Queue<Node<int>>();
            Node<int> current = node;
            queue.Enqueue(current);
            while(queue.Count > 0)
            {
                current = queue.Dequeue();
                Console.WriteLine(current.Data);
                if (current.left != null)
                {
                    queue.Enqueue(current.left);
                }
                if (current.right != null)
                {
                    queue.Enqueue(current.right);
                }
            }
        }

        // 当我们有序的插入数据时 二叉搜索树会退化成链表
        // 平衡二叉树 左右子树高度差不能大于1
    }
}
